package main

import "fmt"

type DoublyLinkedListNode struct {
	data              any
	preNode, nextNode *DoublyLinkedListNode
}

type DoublyLinkedList struct {
	head, tail *DoublyLinkedListNode
}

func (this *DoublyLinkedList) DoublyLinkedListInsertAtHead(data any) {
	if this == nil {
		return
	}
	node := &DoublyLinkedListNode{data: data, nextNode: this.head}
	if this.head != nil {
		this.head.preNode = node
	}
	this.head = node
	if this.tail == nil {
		this.tail = node
	}
}

func (this *DoublyLinkedList) DoublyLinkedListPrintForward() {
	if this == nil {
		return
	}
	curNode := this.head
	for curNode != nil {
		fmt.Printf("%+v", curNode)
		curNode = curNode.nextNode
	}
	fmt.Println()
}

func (this *DoublyLinkedList) DoublyLinkedListPrintBackward() {
	if this == nil {
		return
	}
	curNode := this.tail
	for curNode != nil {
		fmt.Printf("%+v", curNode)
		curNode = curNode.preNode
	}
	fmt.Println()
}

func (this *DoublyLinkedList) DoublyLinkedListAtTail(data any) {
	if this == nil {
		return
	}
	node := &DoublyLinkedListNode{data: data, preNode: this.tail}
	if this.tail != nil {
		this.tail.nextNode = node
	}

	this.tail = node

	if this.head == nil {
		this.head = node
	}

}
func (this *DoublyLinkedList) DoublyLinkedListDel(data any) bool {
	if this == nil {
		return false
	}

	if this.tail != nil && this.head != nil {
		if this.tail.data == data {
			this.tail = this.tail.preNode
			this.tail.nextNode = nil
			return true
		}
		if this.head.data == data {
			this.head = this.head.nextNode
			this.head.preNode = nil
			return true
		}
		curNode := this.head
		for curNode.nextNode != nil {
			if curNode.nextNode.data == data {
				curNode.nextNode = curNode.nextNode.nextNode
				curNode.nextNode.preNode = curNode
				return true
			}
			curNode = curNode.nextNode
		}
	}
	return false
}

func (this *DoublyLinkedList) DoublyLinkedListInsertAfter(index, data any) bool {
	if this == nil {
		return false
	}
	node := &DoublyLinkedListNode{data: data}
	if this.tail != nil && this.head != nil {
		if this.tail.data == index {
			this.DoublyLinkedListAtTail(data)
			return true
		}
		curNode := this.head
		for curNode.nextNode != nil {
			if curNode.data == index {
				node.preNode = curNode
				node.nextNode = curNode.nextNode
				curNode.nextNode = node
				curNode.nextNode.preNode = node
				return true
			}
			curNode = curNode.nextNode
		}
	}

	return false
}

func (this *DoublyLinkedList) DoublyLinkedListIsExist(data any) bool {
	if this == nil {
		return false
	}
	if this.tail.data == data {
		return true
	}
	if this.head.data == data {
		return true
	}
	curNode := this.head
	for curNode.nextNode != nil {
		if curNode.nextNode.data == data {
			return true
		}
		curNode = curNode.nextNode
	}

	return false
}

func (this *DoublyLinkedList) DoublyLinkedListLength() int {
	length := 0
	if this == nil {
		return length
	}
	curNode := this.head
	for curNode != nil {
		length++
		curNode = curNode.nextNode
	}
	return length
}
func DoublyLinkedList_init() {
	fmt.Println("双向链表：")
	ints := []int{1, 2, 3, 4, 5}
	doublyLinkedList := &DoublyLinkedList{}
	for _, i := range ints {
		doublyLinkedList.DoublyLinkedListInsertAtHead(i)
	}
	doublyLinkedList.DoublyLinkedListPrintForward()
	// &{data:5 preNode:<nil> nextNode:0x140000b2060}&{data:4 preNode:0x140000b2080 nextNode:0x140000b2040}&{data:3 preNode:0x140000b2060 nextNode:0x140000b2020}&{data:2 preNode:0x140000b2040 nextNode:0x140000b2000}&{data:1 preNode:0x140000b2020 nextNode:<nil>}
	doublyLinkedList.DoublyLinkedListPrintBackward()
	// &{data:1 preNode:0x140000b2020 nextNode:<nil>}&{data:2 preNode:0x140000b2040 nextNode:0x140000b2000}&{data:3 preNode:0x140000b2060 nextNode:0x140000b2020}&{data:4 preNode:0x140000b2080 nextNode:0x140000b2040}&{data:5 preNode:<nil> nextNode:0x140000b2060}
	doublyLinkedList.DoublyLinkedListAtTail(6)
	doublyLinkedList.DoublyLinkedListPrintForward()
	// &{data:5 preNode:<nil> nextNode:0x1400005c080}&{data:4 preNode:0x1400005c0a0 nextNode:0x1400005c060}&{data:3 preNode:0x1400005c080 nextNode:0x1400005c040}&{data:2 preNode:0x1400005c060 nextNode:0x1400005c020}&{data:1 preNode:0x1400005c040 nextNode:0x1400005c200}&{data:6 preNode:0x1400005c0a0 nextNode:<nil>}
	doublyLinkedList.DoublyLinkedListPrintBackward()
	// &{data:6 preNode:0x1400005c020 nextNode:<nil>}&{data:1 preNode:0x1400005c040 nextNode:0x1400005c200}&{data:2 preNode:0x1400005c060 nextNode:0x1400005c020}&{data:3 preNode:0x1400005c080 nextNode:0x1400005c040}&{data:4 preNode:0x1400005c0a0 nextNode:0x1400005c060}&{data:5 preNode:<nil> nextNode:0x1400005c080}
	doublyLinkedList.DoublyLinkedListDel(6)
	doublyLinkedList.DoublyLinkedListPrintForward()
	// &{data:5 preNode:<nil> nextNode:0x1400005c080}&{data:4 preNode:0x1400005c0a0 nextNode:0x1400005c060}&{data:3 preNode:0x1400005c080 nextNode:0x1400005c040}&{data:2 preNode:0x1400005c060 nextNode:0x1400005c020}&{data:1 preNode:0x1400005c040 nextNode:<nil>}
	doublyLinkedList.DoublyLinkedListDel(5)
	doublyLinkedList.DoublyLinkedListPrintForward()
	// &{data:4 preNode:<nil> nextNode:0x1400005c060}&{data:3 preNode:0x1400005c080 nextNode:0x1400005c040}&{data:2 preNode:0x1400005c060 nextNode:0x1400005c020}&{data:1 preNode:0x1400005c040 nextNode:<nil>}
	doublyLinkedList.DoublyLinkedListDel(3)
	doublyLinkedList.DoublyLinkedListPrintForward()
	// &{data:4 preNode:<nil> nextNode:0x1400005c040}&{data:2 preNode:0x1400005c080 nextNode:0x1400005c020}&{data:1 preNode:0x1400005c040 nextNode:<nil>}
	doublyLinkedList.DoublyLinkedListInsertAfter(4, 5)
	doublyLinkedList.DoublyLinkedListPrintForward()
	// &{data:4 preNode:<nil> nextNode:0x1400005c520}&{data:5 preNode:0x1400005c520 nextNode:0x1400005c040}&{data:2 preNode:0x1400005c080 nextNode:0x1400005c020}&{data:1 preNode:0x1400005c040 nextNode:<nil>}
	doublyLinkedList.DoublyLinkedListInsertAfter(1, 3)
	doublyLinkedList.DoublyLinkedListPrintForward()
	// &{data:4 preNode:<nil> nextNode:0x1400005c520}&{data:5 preNode:0x1400005c520 nextNode:0x1400005c040}&{data:2 preNode:0x1400005c080 nextNode:0x1400005c020}&{data:1 preNode:0x1400005c040 nextNode:0x1400005c5e0}&{data:3 preNode:0x1400005c020 nextNode:<nil>}
	doublyLinkedList.DoublyLinkedListInsertAfter(2, 6)
	doublyLinkedList.DoublyLinkedListPrintForward()
	// &{data:4 preNode:<nil> nextNode:0x1400005c520}&{data:5 preNode:0x1400005c520 nextNode:0x1400005c040}&{data:2 preNode:0x1400005c080 nextNode:0x1400005c6a0}&{data:6 preNode:0x1400005c6a0 nextNode:0x1400005c020}&{data:1 preNode:0x1400005c040 nextNode:0x1400005c5e0}&{data:3 preNode:0x1400005c020 nextNode:<nil>}
	isExist := doublyLinkedList.DoublyLinkedListIsExist(8)
	fmt.Printf("8 isExist %+v\n", isExist)
	// 8 isExist false
	isExist = doublyLinkedList.DoublyLinkedListIsExist(4)
	fmt.Printf("4 isExist %+v\n", isExist)
	// 4 isExist true
	isExist = doublyLinkedList.DoublyLinkedListIsExist(3)
	fmt.Printf("3 isExist %+v\n", isExist)
	// 3 isExist true
	isExist = doublyLinkedList.DoublyLinkedListIsExist(2)
	fmt.Printf("2 isExist %+v\n", isExist)
	// 2 isExist true
	length := doublyLinkedList.DoublyLinkedListLength()
	fmt.Printf("length is %d\n", length)
	// length is 6
	doublyLinkedList.DoublyLinkedListDel(4)
	length = doublyLinkedList.DoublyLinkedListLength()
	fmt.Printf("length is %d\n", length)
	// length is 5
	doublyLinkedList.DoublyLinkedListInsertAtHead(8)
	length = doublyLinkedList.DoublyLinkedListLength()
	fmt.Printf("length is %d\n", length)
	// length is 6
}
